#include <stdio.h>

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int PartSort(int* a, int left, int right)
{
	int key = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[key])
		{
			right--;
		}

		while (left < right && a[left] <= a[key])
		{
			left++;
		}

		Swap(&a[right], &a[left]);	
	}
	Swap(&a[left], &a[key]);
	return left;
}

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int k = PartSort(a, left, right);
	QuickSort(a, left, k - 1);
	QuickSort(a, k + 1, right);
}

int main()
{
	int a[] = { 1,3,5,7,9,2,4,6,8,10 };
	int n = sizeof(a) / sizeof(a[0]);
	QuickSort(a, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	return 0;
}